fejléc
Gyakori kérdések Belépés Új kérdés Véletlen kérdés
Keresés
Kezdőoldal » Számítástechnika » Programozás » Adott ponthoz legközelebbi 2...

Adott ponthoz legközelebbi 2 pont keresése egy ponthalmazból hogyan oldható meg gyorsan?

Figyelt kérdés

Adott "néhány" (nagyságrendileg kb. pár 10000) GPS koordináta (azaz WGS 84)

Hogyan lehet sok (milliárdos nagyságrendű) új adott ponthoz gyorsan megkereseni a fenti listában a 2 legközelebbit? (mármint minden új ponthoz a 2 legközelebbit külön külön)

Nyilván a minden új pontra végigmegyünk a listán és megkeressük a 2 legközelebbit nem egy gyors megoldás. Pláne mert már a távolság számítás is elég lassú önmagában.



#koordináta #algoritmus
ápr. 30. 19:58
 1/10 anonim ***** válasza:
80%
Én először fi szerint rendezném az egész pont halmazt, majd itt megkeresném azokat a pontokat amelyeknél a delta fi a legkisebb. Majd ugyanezt lambdára. Aztán így marad egy "téglalap" amiben azok a pontok vannak amelyeknél esélyes, hogy a legközelebb kerülnek, és ezekből már ki lehet válogatni a két legközelebb esőt, és nem kell minden pont minden ponttól mért távolságát kiszámolni, ami tényleg rengeteg idő.
ápr. 30. 20:51
Hasznos számodra ez a válasz?
 2/10 anonim ***** válasza:
100%
Mármint a lambdára rendezést már csak arra a "sávra" végezném ami az első válogatásból marad, mert ezzel megint lehet csökkenteni a rendezendő adatok mennyiségét.
ápr. 30. 20:52
Hasznos számodra ez a válasz?
 3/10 anonim ***** válasza:
87%

Az is fontos, hogy a két legközelebbinek mi a sorrendje? Lehet valamit tudni a 10k pont eloszlásáról?

A párszor 10k pont alapján előre legenerálnék tartományokat, amire megállapítanám a legközelebbi 2-2 pontot. Ha jó ez az előfeldolgozás, a milliárdnyi pontból már a nagy részére alapból ad megoldást. Aztán a maradéknál meg a legközelebbi párat kell számolni és ellenőrizni.

Lehet olyat is, hogy a 2D teret felosztod egy hálóra (pl. egész koordináták, esetleg hierarchikusan, mint 3D-ben az oktális fánál szokás), és csak az adott részben és a szomszédosokban lévőtől kell távolságot számolnod.

ápr. 30. 22:06
Hasznos számodra ez a válasz?
 4/10 anonim ***** válasza:
83%
#4 én a hálóra szavazok, az a legtisztább és leggyorsabb megoldás. Lehet fancy algoritmusokat alkotni, de mi értelme van, mikor a hálós megoldás biztosan gyorsabb ÉS érthetőbb?
máj. 1. 00:01
Hasznos számodra ez a válasz?
 5/10 anonim ***** válasza:
82%

A probléma a legközelebbi szomszéd keresése:

[link]

a szimpla listában/tömbben való lineáris keresés helyett léteznek hatékonyabb megoldások, mint például az "oszd meg és uralkodj" módszere:

[link]

illetve a különböző térparticionáló fák:

[link]

alkalmazása.

máj. 1. 01:33
Hasznos számodra ez a válasz?
 6/10 anonim ***** válasza:

"illetve a különböző térparticionáló fák:

[link]

alkalmazása."


+1

máj. 1. 03:14
Hasznos számodra ez a válasz?
 7/10 A kérdező kommentje:

Köszönöm a válaszokat. Átnézem.


#4: Igen, számít a sorrend, de ha már megvan a 2 legközelebbi, akkor azt a 2-t már össze tudom hasonlítani.

Ezek (10k pont) gyakorlatilag útvonalak európán belül (azaz az útvonalakon kb. 50-200 méterenként, de néhol kb. 0.5-2 kilométerenként pozíciók... néhol 1-1 kimarad, tehát ott dupla a távolság).

Lehet, hogy kézzel javítani kellene ezeket a hibákat, de az a gond, hogy ezek valahonnan "jönnek" és bár ritkán de módosulnak (pár havonta-évente). Az igazi javítás a forrásnál kéne, de ez nem a mi hatáskörünk.


A többi pont nagyon nagy részben az utakon vagy közelükben álló vagy mozgó jeladókról érkezik 1 másodperc-3 percenként.


Ezen pontok nagy része Magyarország vagy pár 100 km-es környezetében van. Lehet némelyik messzebb is, de ott igazából nem is releváns, hogy helyes eredményt adjon az algoritmus.

máj. 1. 09:32
 8/10 anonim ***** válasza:

Ha a pontjaid sorban jönnek, és nem tudnak teleportálni, még egyszerűbb a helyzeted. Akkor elég a - néhány - közeli referenciapontot megjegyezni, és ha az előző ponttól a mostani nincs messze, elég azokhoz viszonyítani. Ez még a hálónál/fánál is gyorsabb lesz. (mondjuk tudod a 10 legközelebbi referenciapontot, és ha az előző ponttól nem vagy messze, és ennek a 10 pontnak a távolságának a sorrendje ugyanaz, a megoldás is ugyanaz marad)

Ha a jeladóknak van valami azonosítója, akkor jeladónként memóriában tudod tartani ezeket, még egyszerűbb dolgod van. Persze ha változik a sorrend, akkor fallbackelsz az előző algoritmusra. (a 10-et meg hasraütésből írtam, át kell gondolni, hogy - az egyszerűség kedvéért - gömbön mi a legrosszabb eset, amikor rossz referenciapontot találna)

Ha 3 perce valahol Nagyszalonta és Geszt között voltam, valószínűleg most is.

máj. 3. 00:03
Hasznos számodra ez a válasz?
 9/10 A kérdező kommentje:

Felosztottam a "síkot" 0.01*0.01 fokos részekre és mindegyikhez előre kiszámoltam, hogy mely pontok lehetnek a 2 legközelebbi között. (Nyilván ez nem csak 2 pont lehet, mert tartalmazza az összes benne lévő pontot - ami általában max 1, nagyon ritkán több... és attól függően, hogy melyik oldalához van közel egy külső pont még több külső pont is lehet)

Eléggé felgyorult :)


Ami korábban 6,5 napig futott, az most kevesebb mint 10 óraig tartott. Ez egyébként még nem a teljes adat amit fel kell dolgozni időnként, az erededtileg 19 napig futtot, tehát most várhatóan 30 óra alatt befejezi.


Bár a kezedti "térkép" kiszámítás kb. 5 percig fut, de az nem számít :)

máj. 12. 11:31
 10/10 anonim ***** válasza:
De az ugye megvan, hogy a koordinátában rendszer van, tehát sorba rendezhetőek az adatok? Ergo a legközelebbi pontok a listában ott vannak egymás mellett... Ha jön egy új koordináta, akkor csak a helyét kell megkeresni a listában, ami egyértelműen determinálható, hogy hol van. Mivel a kimenet a legközelebbi pont, ezért keresni nem kell semmit. Egyszerűen a szomszédos pontok közül kell csak távolságokat számolni és kiválasztani a legközelebbit. Ha előre gondolkodsz, akkor a szomszédos távolságok eleve tárolva vannak.
máj. 13. 07:03
Hasznos számodra ez a válasz?

További kérdések:

Számítástechnika főkategória kérdései »
Számítástechnika - Programozás kategória kérdései »




Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!